// 优先级队列
// 数组中每次都需要拿到最大元素或者最小元素，可以考虑用堆的思想解决
// top K 问题要想到用堆解决
// top K 问题有可能需要预处理数组，例如统计单词出现的次数，可以借助哈希表完成
// 中位数问题 - 可以考虑用大小堆来解决

// 例题 4：
// 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
//
//        例如 arr = [2,3,4] 的中位数是 3 。
//        例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
//        实现 MedianFinder 类:
//
//        MedianFinder() 初始化 MedianFinder 对象。
//
//        void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
//
//        double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
//
//        示例 1：
//
//        输入
//        ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
//        [[], [1], [2], [], [3], []]
//        输出
//        [null, null, null, 1.5, null, 2.0]
//
//        解释
//        MedianFinder medianFinder = new MedianFinder();
//        medianFinder.addNum(1);    // arr = [1]
//        medianFinder.addNum(2);    // arr = [1, 2]
//        medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
//        medianFinder.addNum(3);    // arr[1, 2, 3]
//        medianFinder.findMedian(); // return 2.0
//        提示:
//
//        -105 <= num <= 105
//        在调用 findMedian 之前，数据结构中至少有一个元素
//        最多 5 * 104 次调用 addNum 和 findMedian

// 解题思路：
// 利用大根堆维护左边区间
// 利用小根堆维护右边区间
// 始终保持左边元素数量等于或比右边元素数量多 1

import java.util.PriorityQueue;

public class MedianFinder {
    PriorityQueue<Integer> heap1;
    PriorityQueue<Integer> heap2;

    public MedianFinder() {
        heap1 = new PriorityQueue<>((a, b) -> b - a);
        heap2 = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if(heap1.isEmpty()) heap1.offer(num);
        else{
            if(num <= heap1.peek()){
                heap1.offer(num);
                if(heap1.size() - heap2.size() > 1) heap2.offer(heap1.poll());
            }else{
                heap2.offer(num);
                if(heap2.size() > heap1.size()) heap1.offer(heap2.poll());
            }
        }
    }

    public double findMedian() {
        if(heap1.size() > heap2.size()) return (double)heap1.peek();
        else return (heap1.peek() + heap2.peek()) / 2.0;
    }
}
